This invention relates to a data processor, a communication system and a recording medium and particularly, to a data processor, a communication system and a recording medium suitable for encryption and decryption of data.
Data encryption using a computer has widely been adopted in recent years.
Encryption algorithms for this purpose are in a broad sense segmented into a block cipher in which data are segmented into a set of blocks each in a given length and encryption is conducted for each block as a unit, and a stream cipher in which the input data is encrypted one character by one character. There is a difference between a block cipher and a stream cipher: while the same input of a block cipher is transformed into the same output of the block cipher, in a case of a stream cipher, even the same input is transformed into a different output.
As a conventional block cipher, only a cryptosystem has been known in which a length of input/output is fixed and no cipher with a variable input/output length has been realized. In a conventional method, in order to encrypt a variable-length input, there is no way but to encrypt blocks one by one or to chain encrypted blocks.
As a cryptosystem in which a variable-length input is encrypted, a operation mode is famous. In this method, an input whose length does not coincides with a multiple of a block length is provided with padding wherein a block of the input with a length shorter than a given block length has padding with a proper bit size so that the input is divided into a plurality of blocks with the given block length. However, in this method, since encryption has to be performed after adjustment of a block length, a problem arises due to reduction in transmission efficiency.
On the other hand, since a block cipher has a nature that the same input gives the same output, there arises a fault that a block length cannot be short. The reason is that when a block length is short, an input table corresponding to an output thereof can be formed. If such a table has been formed, information can be taken out from a cipher text by decrypting the cipher text into an original plain text without knowledge of a key.
A stream cipher can be regarded as a random number generator, since a random number sequence output by the same initial value (key) is different and an initial value is hard to be traceable from the random number sequence. While this point is a base of the security of a steam cipher, if the same key is continued to be used, random number sequences themselves are finally known to an attacker and thereby a cipher has a risk to be decrypted even without knowledge of a key. A block cipher with an increased length of a block can be considered a solution to avoid such a problem inherent to a stream cipher.
Herein, a case where a comparatively short communication message is encrypted will be discussed. If a communication message is long, reduction in transmission efficiency caused by padding in a block cipher is not problematic. However, a comparatively short message has a chance in which reduction in transmission efficiency is seriously problematic.
For example, in a charging system in which payment is due for each received program as in the case of a satellite broadcast, the charging system is realized by a individual information, which is transmitted only to a contracted user, and which is prepared by encrypting a key obtained through encrypting a program itself with a user key. Since individual information is constituted of blocks each with a comparatively short length and the number of individual information units is large, reduction in transmission caused by padding is a great problem. If high transmission efficiency is desired, it is necessary for a block length to be short so as to make padding smaller, which arises another problem to reduce a degree of security.
Of the above-described problems, a problem relating to transmission efficiency is solved by using a stream cipher, but if a stream cipher is used, there is a necessity for a key to be frequently changed in order to increase a degree of security, which pushes a cost upward tremendously.
On the other hand, Nyberg et al. has proposed a method for constructing a secure substitution table for a block cipher which is required for designing a secure DES cryptosystem, that is, a Feistel type cipher. That is, Nyberg et al. has shown that if a substitution table is prepared so as to have a nature called APN (Almost Perfect Non-liner), a cipher which has a provable security against a typical cipher attacking method, such as a differential cryptanalysis or a linear cryptanalysis can be created.
Therefore, it has been desired means in which a block cryptosystem in which a message is transformed not to a steam cipher, but to a Feistel type cipher for which a design policy proposed by Nyberg et al. is applicable is employed and the messages are encrypted with high efficiency, even when many comparatively short communication messages, which is described above, are encrypted.
The present invention has been made in consideration of such circumstances and accordingly, it is a first object of the present invention to provide a data processor, a communication system and a recording medium by which even when a block length of a block cipher is short, not only is reduction in security due to shortness of a block length prevented from occurring, but transmission efficiency is also increased and a Feistel type cipher is prepared.
Further, it is a second object of the present invention to provide a data processor, a communication system and a recording medium in which a block length itself can be variable.
The present invention has been made in order to achieve such an object.
According to a first aspect of the present invention, therein a provided a data processor comprising:
a transformation section in which small blocks which are obtained by sequentially segmenting at least one of a plain text and a cipher text from a leading edge thereof are transformed with keys;
a mutual action section in which the small blocks transformed in the transformation section and another small blocks mutually act on each other; and
a chaining section in which the small blocks transformed in the transformation section are chained with another small blocks not adjacent to the small blocks transformed in the transformation section.
Since the present invention is provided with such means, a mutual action between small blocks is made possible and further chaining is also performed between small blocks of each pair in a proper manner, a degree of robustness of a cryptosystem can be increased.
Besides, since the same effect as in a case where a length of a small block is actually longer can be obtained by the chaining, a degree of robustness against cryptosystem can be prevented from being reduced even if a length of a small block is short.
According to a second aspect of the present invention, there is provided a data processor of the first aspect,
wherein, of the small blocks obtained by segmenting at least one of the plain text and the cipher text, odd-numbered small blocks counted from a leading edge of the small blocks obtained by segmenting at least one of the plain text and the cipher text and small blocks following the odd-number small blocks are named as odd-numbered small column blocks, even-numbered small blocks counted from the leading edge of the small blocks obtained by segmenting at least one of the plain text and the cipher text and small blocks following the even-number small blocks are named as even-numbered small column blocks, and
the mutual action section causes the odd-numbered small column blocks to mutually act with the even-numbered column blocks and the chaining section causes the odd-numbered small column blocks to mutually act with each other and causes the even-numbered small column blocks to mutually act with each other.
Since such means are provided in the present invention, a cryptosystem in which a mutual action occurs between small blocks respectively of an odd-numbered column and an even-numbered column can be realized. Therefore, for example, a Feistel type cipher can be attained between odd- and even-numbered columns. Further, since a chaining action is performed between odd- and even-numbered columns, the above-described mutual action between a pair of odd- and even-numbered columns are scaled up to be an overall mutual action between the whole group of odd-numbered columns and the whole group of even-numbered columns.
Further, a degree of robustness of a cryptosystem can be retained by a chaining action even if a length of a small block is shorter. Therefore, even if a plain text before segmentation into small blocks is short, efficient encryption can be realized with small blocks short in length.
Even if a block length is short in block encryption in such a manner, not only reduction in security due to shortness of a block length is prevented from occurring, but a transmission efficiency can also be increased and a Feistel type encryption is further made possible.
Besides, when the number of chaining of small blocks is changed, a length of a block composed of plural small blocks (referred to as a segmented block in embodiments) can be variable.
Further, according to a third aspect of the present invention, there is provided a data processor of the second aspect,
wherein a chaining direction in the chaining section is a forward direction of columns; and
each of odd-numbered columns and even-numbered columns has the transformation section at a single row or more.
Therefore, a degree of robustness of cryptosystem and a processing time period can be adjusted by changing the number of rows.
Further, according to a fourth aspect of the present invention, there is provided a data processor of the third aspect,
wherein the number of rows at which transformation sections are located, the transformation sections being included in the odd-numbered column and the even-numbered column, is decreased with increase in the number of the odd-numbered columns and the even-numbered columns.
Formations of a chaining between small blocks are sequentially conducted from the leading position of an encryption/decryption object. For example, a result of first transformation means is input to a second closest column from the first transformation means to perform an exclusive OR with a small block in the second closest column. This processing is sequentially repeated on every two column.
In a case where such chaining processing is sequentially performed, processing results of columns are sequentially output after processing in each column. Therefore, if the number of processing rows at which transformation means operate is decreased in a part where the number of columns is large, an overall processing speed can be increased. In the mean time, since an effect of randomized data bits or the like by a chaining is higher as the number of columns is large, the number of rows in the part is decreased with a little adverse influence on robustness of a cipher.
Further, according to a fifth aspect of the present invention of the present invention, there is provided a data processor of the third aspect,
wherein the chaining direction of the chaining section is switched from a forward direction of columns to a backward direction thereof when the number of rows at which the transformation sections are located reaches a prescribed number.
When such a chaining is realized, an effect of randomized data bits can be high not only in a part where the number of column is large, but in a part where the number of column is small, which contributes to further increase in robustness of a cryptosystem.
Further, according to a sixth aspect of the present invention there is provided a data processor of the third aspect,
wherein processing in the transformation sections other than transformation sections where a dependence relationship arises due to processing in the mutual action section and processing in the chaining section is performed in parallel.
With such means provided, the present invention can realized efficient processing.
Further, according to a seventh aspect of the present invention, there is provided a data processor of the second aspect,
wherein at least one of a length of the small blocks and the number of chaining of the small blocks is variable.
With such means provided, the present invention can freely change a length of a segmented block composed of a plurality of small blocks while a robustness of a cryptosystem is retained.
Further, according to an eighth aspect of the present invention, there is provided a communication system comprising:
a first communication system for transmitting a cipher by using the data processor of the second aspect; and
a second communication system for decrypting the cipher transmitted from the first communication system to a plain text by using the data processor of the second aspect,
wherein a block length of the which is determined by a length of the small block and the number of chaining of small blocks is shared between the first and second communication systems.
With such means provided, the present invention can enjoy not only effects of the data processors according to any of the second to sixth aspects of the present invention but a cryptosystem with a higher degree of difficulty in deciphering can be obtained through keeping a block length in secret.
Further, according to a ninth aspect of the present invention, there is provided a communication system of the eighth aspect,
wherein the block length is variable in each of the small blocks.
Further, according to a tenth aspect of the present invention, there is provided a communication system of the ninth aspect, further comprising:
a random number generator for determining the block length based on a seed which is shared by the first and second communication systems.
Since the present invention is provided with such means, a block length is harder to be found by a third party, which enables a robustness of a cryptosystem to be further reinforced.
Further, according to an eleventh aspect of the present invention, there is provided a communication system of the eighth aspect,
wherein a timing in which a direction of a chaining is switched is shared by the first and second communication systems.
Since the present invention is provided with such means, a way of chaining can be secret and thereby a robustness of a cryptosystem can be further strengthened.
Additional objects and advantages of the invention will be set forth in the description which follows, and in part will be obvious from the description, or may be learned by practice of the invention. The objects and advantages of the invention may be realized and obtained by means of the instrumentalities and combinations particularly pointed out hereinafter.